/*!
 * \file vEBTree.h
 * \brief A van Emde Boas tree data structure, implemented with a simple array of words.
 *
 * \date Jun 18, 2012
 * \author correa
 */
#ifndef ARRAYVEBTREE_H_
#define ARRAYVEBTREE_H_

#include<string.h>//necessary to use memset
#include<cstdio>
#include <stdlib.h>
#include "BitTools.h"
#include"vEBTree.h"

template<typename T> class ArrayvEBTreeFactory;

/*!
 * \brief Implementation of vEBTree using a array of words.
 *
 * This class is derived from eVBTree, implemented with a simple array of word as data structure. All the pure virtual
 * methods of vEBTree are implemented and same methods are overwritten in order to make a better use of the array
 * structure.
 *
 * In the base array, which bit index a element of the universe and the upper levels indexs words in the level
 * bellow. For example the vector in the level 1 has a bit to every word in the level 0 vector. For the base
 * array(the array at level 0) the i-th represents wherever or not a element is in the set, if it belongs to
 * the set the i-th bit has the value 1, if not the value 0. For the other levels the i-th bit represents if the
 * i-th word in the bellow array is null or not, if it is null the i-th bit has the value 0 and 1 if it is not.
 *
 * This class is a van Emde Boas tree with implemented as array of words.
 */
template <typename T>
class ArrayvEBTree : public vEBTree<T> {
private:
	T* vector;//!< the array of words
	long vectorsz;//!< the size of vector

	long bitLeast(long idx, long slide, long h);

public:

	/*! \class Iterator
	 * \brief A generic iterator on the set of elements.
	 *
	 * The elements are enumerated in an increasing order.
	 *
	 * An object of this class keeps the state of an enumeration. This means that various enumerations can
	 * be performed simultaneously provided that each of them is associated with a different iterator.
	 *
	 * The path from the root of the tree until last element enumerated is composed by nodes of the vEBTree.
	 * A binary search in this path using min and max information of subtrees allows a \f$O(\log \log n)\f$
	 * time complexity for each access.
	 *
	 */
	class Iterator : public OrderedSet<long>::Iterator{
		friend class ArrayvEBTree;

		protected:
			int ht;//!< a copy of the target instance of vEBTree<T>::height.

			T** levels;//!< a copy to the levels in the tree.

			long* slides;//!< position inside the word, in each level.

			long* idxs;//!< indexes, in each level of the words enumerated.

			long* lims;// !< the size of each level.

			long logb;// !< the log of the word size.

			long word_size;//!< the size in bits of a word

			long size;//!< the size of the vEBTree that is being enumerate, its a simple copy of the value t->size().

			long current;//!< the current element in the enumeration

			/*!
			 * \brief A constructor for a Iterator over a specified vEBTree.
			 *
			 * Create a Iterator to look up a specified vEBTree. The Iterator enumerate
			 * all the elements in the set represented by the object passed as parameter.
			 *
			 * \param t the specified tree.
			 */
			Iterator(ArrayvEBTree<T> * t);

			long bitLeast(long idx, long slide, long h);

		public:
			/*!
			 * \brief The destructor.
			 */
			virtual ~Iterator();

			/*!
			 * \brief Start enumeration.
			 *
			 * Initailize all the variables and start a enumeration of the elements in the set.
			 *
			 * The variables idx and slide are set to zero and the initial word is set to be
			 * the first non null word.
			 */
			virtual void start();


			/*!
			 * \brief Restart enumeration.
			 *
			 * Restart the enumeration. It will lost all the current state and it will start over the
			 * enumeration.
			 *
			 * Usually it is a simple call to start().
			 *
			 * \see start()
			 *
			 */
			virtual void restart();

			/*!
			 * \brief Restart enumeration from a specified element.
			 *
			 * Restart the enumeration. it will lost all the current state and it will
			 * start over from the smalest element in the set that is bigger or equal
			 * than the specified element.
			 *
			 * If the specified element is not a element of the universe a error will
			 * occur.
			 *
			 * \param the specified element
			 */
			virtual void restartFrom(long i);

			/*!
			 * \brief Determine if still there is a element in the set not enumerated yet.
			 *
			 * This method determine if there is a element in the set not enumerate yet. It look
			 * in all the leaf level of the tree using the information of the other levels.
			 *
			 * We start the search in the word of the least enumerated element. If it has other bit 1
			 * we return this value. If not we look in the upper level for the next non null word and so
			 * go on untill the top level where we make a serial search.
			 *
			 * \return true if there is a element not enumerated yet, and false otherwise.
			 */
			virtual bool hasNext();

			/*!
			 * \brief Index of the next element in the set according to the current enumeration.
			 *
			 * The next element in the current enumeration. The order is the natural order between the natural
			 * numbers.
			 *
			 * \return the next element, if exists one; otherwise, a value greater or equal to the size of the universe.
			 */
			virtual long next();
		};

	/*! \class Iterator
	 * \brief A filtered iterator on the set of elements.
	 *
	 * The elements are enumerated in an increasing order, but only the ones that belong
	 * to the filter as well.
	 *
	 * An object of this class keeps the state of an enumeration. This means that various enumerations can
	 * be performed simultaneously provided that each of them is associated with a different iterator.
	 *
	 * The path from the root of the tree until last element enumerated is composed by nodes of the vEBTree.
	 * A binary search in this path using min and max information of subtrees allows a \f$O(\log \log n)\f$
	 * time complexity for each access.
	 *
	 */
	class FilterIterator : public OrderedSet<long>::Iterator{
		friend class ArrayvEBTree;

		protected:
			OrderedSet<long>* filter;//!< the filter to enumeration

			int ht;//!< a copy of the target instance of vEBTree<T>::height.

			T** levels;//!< a copy to the levels in the tree.

			long* slides;//!< position inside the word, in each level.

			long* idxs;//!< indexes, in each level of the words enumerated.

			long* lims;// !< the size of each level.

			long logb;// !< the log of the word size.

			long word_size;//!< the size in bits of a word

			long size;//!< the size of the vEBTree that is being enumerate, its a simple copy of the value t->size().

			long current;//!< the current element in the enumeration

			/*!
			 * \brief A constructor for a Iterator over a specified vEBTree.
			 *
			 * Create a Iterator to look up a specified vEBTree. The Iterator enumerate
			 * all the elements in the set represented by the object passed as parameter.
			 *
			 * \param t the specified tree.
			 *
			 * \param filter the filter to the correspondent enumeration
			 */
			FilterIterator(ArrayvEBTree<T> * t, OrderedSet<long>* filter);

			/*!
			 * \brief Determine the first bit 1 in the word of index idx in the
			 * vector of level h, after the specified position.
			 *
			 * \param idx the index of the word to be search.
			 *
			 * \param slide the especified position.
			 *
			 * \param h the height of the tree.
			 *
			 * \return
			 */
			long bitLeast(long idx, long slide, long h);

		public:
			/*!
			 * \brief The destructor.
			 */
			virtual ~FilterIterator();

			/*!
			 * \brief Start enumeration.
			 *
			 * Initailize all the variables and start a enumeration of the elements in the set.
			 *
			 * The variables idx and slide are set to zero and the initial word is set to be
			 * the first non null word.
			 */
			virtual void start();


			/*!
			 * \brief Restart enumeration.
			 *
			 * Restart the enumeration. It will lost all the current state and it will start over the
			 * enumeration.
			 *
			 * Usually it is a simple call to start().
			 *
			 * \see start()
			 *
			 */
			virtual void restart();

			/*!
			 * \brief Restart enumeration from a specified element.
			 *
			 * Restart the enumeration. it will lost all the current state and it will
			 * start over from the smalest element in the set that is bigger or equal
			 * than the specified element.
			 *
			 * If the specified element is not a element of the universe a error will
			 * occur.
			 *
			 * \param the specified element
			 */
			virtual void restartFrom(long i);

			/*!
			 * \brief Determine if still there is a element in the set and in the filter not enumerated yet.
			 *
			 * This method determine if there is a element in the set and in the filter not enumerate yet. It look
			 * in all the leaf level of the tree using the information of the other levels.
			 *
			 * We start the search in the word of the least enumerated element. If it has other bit 1
			 * we return this value. If not we look in the upper level for the next non null word and so
			 * go on untill the top level where we make a serial search.
			 *
			 * \return true if there is a element not enumerated yet that belongs to the set and the filter
			 * , and false otherwise.
			 */
			virtual bool hasNext();

			/*!
			 * \brief Index of the next element in the set according to the current enumeration.
			 *
			 * The next element in the current enumeration. The order is the natural order between the natural
			 * numbers.
			 *
			 * \return the next element, if exists one; otherwise, a value greater or equal to the size of the universe.
			 */
			virtual long next();
		};

	/*!
	 * \brief The index of the specified element in the vector of words.
	 *
	 * This value is given by the floor of the specified element divided by the size of a word.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the specified element in the vector of words.
	 *
	 */
	virtual long wordIdx(long i);

	/*!
	 *
	 * \brief The index of the specified element in a word.
	 *
	 * This value is given by the remainder of the specified element divided by the size of a word.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the specified element in a word.
	 *
	 */
	virtual long inWordIdx(long i);

	/*!
	 * \brief The node in the index i of the leaf level of the tree.
	 *
	 * This method should be implemented in each child class. It is to be used used for the
	 * methods in the father class as a way to retrieve nodes in each level of the tree, that
	 * is a vEBTree of only one level.
	 *
	 * \param i the index of the node to be retrieve.
	 */
	virtual T treeNode(long i);

	/*!
	 * \brief Change the value of the i-th word in the array of words
	 *
	 * Change the value of the i-th word in the array of words to the specified
	 * value. This change also affects the upper levels of the tree.
	 *
	 * If the new node is non null the bit that represents the word in the
	 * position i in the immediate upper level is set to 1, if the new node is
	 * null the bit is set to 0.
	 *
	 * \param i the index of the word to be modified in the vector
	 * \param the specified value to the add at the vector of words.
	 *
	 * \return true if the change sucessed and false otherwise
	 *
	 */
	virtual bool setNode(long i, T newnode);

	/*!
	 * \brief Change the value of the i-th word in the array of words
	 * without update any information in the other levels.
	 * Change the value of the i-th word in the array of words to the specified
	 * value.
	 *
	 * If the new node is non null the bit that represents the word in the
	 * position i in the immediate upper level is set to 1, if the new node is
	 * null the bit is set to 0.
	 *
	 * \param i the index of the word to be modified in the vector
	 * \param the specified value to the add at the vector of words.
	 *
	 * \return true if the change sucessed and false otherwise
	 *
	 */
	virtual bool setNodeInLevel(long i, T newnode);

	/*!
	 * \brief Determine the first bit 1 after the i-th bit in the word that the i-th bit belongs
	 *
	 * Determine the set bit 1 after the i-th bit in the word that the i-th bit belongs. This is
	 * implement with a builtin function to insure a fast operation.
	 *
	 * If the valeu specified is not a member of the universe an error will occur.
	 *
	 * \param the position of the specified bit in the vector.
	 *
	 * \return the position of the first bit 1 after the i-th bit in the word that i-th belongs.
	 * If there is not a such bit it will return -1.
	 */
	virtual long nextSetInWord(long i);

	/*!
	 * \brief Determine the first bit 1 in the array of words.
	 *
	 * Determine the first bit 1 in the vector of words. This is
	 * implement with a builtin function to insure a fast operation.
	 *
	 * If the valeu specified is not a member of the universe an error will occur.
	 *
	 * \param the position of the specified bit in the vector.
	 *
	 * \return the position of the first bit 1 after the i-th bit in the word that i-th belongs.
	 * If there is not a such bit it will return -1.
	 */
	virtual long firstSetInWord(long i);

	/*!
	 * \brief Determine the first bit 0 in the array of words.
	 *
	 * Determine the first bit 0 in the vector of words. This is
	 * implement with a builtin function to insure a fast operation.
	 *
	 * If the valeu specified is not a member of the universe an error will occur.
	 *
	 * \param the position of the specified bit in the vector.
	 *
	 * \return the position of the first bit 0 after the i-th bit in the word that i-th belongs.
	 * If there is not a such bit it will return -1.
	 */
	virtual long firstComplInWord(long i);

	/*!
	 * \brief Determine the first bit 0 after the i-th bit in the word that the i-th bit belongs
	 *
	 * Determine the set bit 0 after the i-th bit in the word that the i-th bit belongs. This is
	 * implement with a builtin function to insure a fast operation.
	 *
	 * If the valeu specified is not a member of the universe an error will occur.
	 *
	 * \param the position of the specified bit in the vector.
	 *
	 * \return the position of the first bit 0 after the i-th bit in the word that i-th belongs.
	 * If there is not a such bit it will return -1.
	 */
	virtual long nextComplInWord(long i);

	/*!
	 * \brief Count the number of bits 1 in the specified word
	 *
	 * Count the number of bits 1 in the specified word. If the value
	 * is not a valid an error will occur.
	 *
	 * This is implemented with a builtin function to insure a very fast
	 * operation with a simgle word.
	 *
	 * \param i the specified word
	 *
	 * \return the number of bits 1 in the specified word
	 */
	virtual long countSetInWord(long i);

	/*!
	 * \brief Count the number of bits 0 in the specified word
	 *
	 * Count the number of bits 0 in the specified word. If the value
	 * is not a valid an error will occur.
	 *
	 * This is implemented with a builtin function to insure a very fast
	 * operation with a simgle word.
	 *
	 * \param i the specified word
	 *
	 * \return the number of bits 0 in the specified word
	 */
	virtual long countComplInWord(long i);

	/*!
	 * \brief Change the value to the specified bit to 1
	 *
	 * Change the value of the specified bit to 1 without update the information
	 * in the upper levels of the tree. This method is used internally in the structure
	 * to make fast changes of intermediary values.
	 *
	 * If the specified bit is not in the vector an error will occur.
	 *
	 * \param i the position of the specified bit
	 */
	virtual void toSetInLevel(long i);

	/*!
	 * \brief Change the value to the specified bit to 0
	 *
	 * Change the value of the specified bit to 0 without update the information
	 * in the upper levels of the tree. This method is used internally in the structure
	 * to make fast changes of intermediary values.
	 *
	 * If the specified bit is not in the vector an error will occur.
	 *
	 * \param i the position of the specified bit
	 */
	virtual void toComplInLevel(long i);

	/*!
	 * \brief Change the value of all bits to 1
	 *
	 * Change the value of all bits to 1 without update the information
	 * in the upper levels of the tree. This method is used internally in the structure
	 * to make fast changes of intermediary values.
	*/
	virtual void allToSetInLevel();

	/*!
	 * \brief Change the value of all bits to 0
	 *
	 * Change the value of all bits to 0 without update the information
	 * in the upper levels of the tree. This method is used internally in the structure
	 * to make fast changes of intermediary values.
	*/
	virtual void allToComplInLevel();

public:

	/*!
	 * \brief Start a new iterator for the set represented by this object.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 *
	 * \return a iterator over the set represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newSetIterator(){
		return new Iterator(this);
	}

	/*!
	 * \brief Start a new iterator for the set represented by this object with a filter.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 * The enumeration is filtered by the set passed as parameter.
	 *
	 * \param filter a filter to eliminate same elements of the enumeration.
	 *
	 * \return a iterator over the set represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newSetIterator(OrderedSet<long>* filter){
		return new FilterIterator(this, filter);
	}

	/*!
	 * \brief The base constructor of the class.
	 *
	 * The universe is always a set of natural numbers, starting from 0 until sz-1.
	 *
	 * \sa vEBTree(int size)
	 *
	 * \param sz the number of elements in the universe.
	 */
	ArrayvEBTree(int sz);

	/*!
	 * \brief The constructor of the class.
	 *
	 * The universe is always a set of natural numbers, starting from 0 until sz-1.
	 *
	 * \sa vEBTree(int size)
	 *
	 * \param sz the number of elements in the universe.
	 *
	 * \param ht the number of upper levels in the tree.
	 */
	ArrayvEBTree(int size, int ht);

	/*!
	 * \brief A destructor.
	 *
	 * All data used are deleted and memory space are cleaned.
	 */
	virtual ~ArrayvEBTree();

	/*!
	 * \brief Create a copy of this object.
	 *
	 * A concrete implementation of this class must override this method in order to perform the copy of the
	 * data structure.
	 *
	 * \return a copy of this object.
	 */
	virtual OrderedSet<long>* clone();

	/*!
	 * \brief Determine the next element in the set of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set).
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe.
	 */
	virtual long nextSetElement(long i);

	/*!
	 * \brief Determine the next element in the set, in increasing order, of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set). If the element specified is not in the universe an error will occur.
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe is returned.
	 */
	long nextSetElementInLevel(long i);

	/*!
	 * \brief Determine the next element in the set, in increasing order, of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set).  If the element specified is not in the universe an error will occur.
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe is returned.
	 */
	long nextComplElementInLevel(long i);

	/*!
	 * \brief Add the specified element to the set, removing it from the complement.
	 *
	 * As a result of this operation, the specified element appears in an enumeration of the set.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toSet(long i);

	/*!
	 * \brief Add the specified element to the complement, removing it from the set.
	 *
	 * As a result of this operation, the specified element disappears in an enumeration of the set.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toCompl(long i);


	/*!
	 * \brief Determines whether the specified element is in this set.
	 *
	 * Determine if the bit correspondent to the specified element is 1.
	 *
	 * If the specified element is not valid, an error will occur.
	 *
	 * \param i the specified element.
	 *
	 * \return \c true if \c i is in the set, and \c false otherwise.
	 */
	virtual bool isInSet(long i);

	/*!
	 * \brief Determines whether the specified element is in this complement.
	 *
	 * Determine if the bit correspondent to the specified element is 1.
	 *
	 * If the specified element is not valid, an error will occur.
	 *
	 * \param i the specified element.
	 *
	 * \return \c true if \c i is in the complement, and \c false otherwise.
	 */
	virtual bool isInCompl(long i);


	/*!
	 * \brief Returns an array containing all of the elements in this set in increasing order.
	 *
	 * At the discretion of the implementation, this object may maintain a reference to the returned array.
	 *
	 * The size of the vector is returned in the pointer size.
	 *
	 * \param size a pointer to store the number of elements in the set.
	 *
	 * \return an array containing all the elements in this vEBTree.
	 *
	 */
	virtual long* toArray(long* size);

	/*!
	 *  \brief The number of elements present in the universe.
	 *
	 *  This is the value passed as parameter to the constructor, it is important to notice that
	 *  this is not the real size of the tree, actually the real size of the tree is about \f$ 2size\f$.
	 *
	 *  \return the number of bits used to index all the elements of the universe.
	 */
	virtual long size();

	/*!
	 * \brief The size of the vector of words
	 *
	 * it returns the size of the vector used to store the information about the set.
	 * This is the number of words used in the array to represent the whole universe it
	 * is not necessary the real size of the array.
	 *
	 *\return the number of words used to represent the whole universe.
	 */
	virtual long sizeInWord();

	/*!
	 *  \brief Add all the elements of the universe to the set.
	 *
	 * Implemented using allToSetInLevel() in each level.
	 *
	 *\see allToSetInLevel()
	 */
	virtual void allToSet();

	/*!
	 *  \brief Add all the elements of the universe to the complement.
	 *
	 * Implemented using allToComplInlevel().
	 *
	 * \see allToComplInLevel().
	 */
	virtual void allToCompl();

	virtual bool isEmpty();

	/*!
	 * \brief The operation of union between the set represented by this object and the
	 * set represented by v.
	 *
	 * This method has the same semantic of setUnionSet in the vEBTree, but it is
	 * definied to make use of the array structure of this class and get direct acess
	 * to the data structure.
	 *
	 * \param v the set to be operated.
	 */
	virtual void setUnionSet(ArrayvEBTree<T>* v);

	/*!
	 * \brief The operation of union between the set represented by this object and the
	 * set represented by v.
	 *
	 * This method has the same semantic of setUnionSet in the vEBTree, but it is
	 * definied to make use of the array structure of this class and get direct acess
	 * to the data structure.
	 *
	 * \param v the set to be operated.
	 */
	virtual void setUnionSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* ret);

	/*!
	 * \brief The operation of union between the set represented by this object and the
	 * set represented by v.
	 *
	 * This method has the same semantic of setIntersecSet in the vEBTree, but it is
	 * definied to make use of the array structure of this class and get direct acess
	 * to the data structure.
	 *
	 * \param v the set to be operated.
	 */
	virtual void setIntersecSet(ArrayvEBTree<T>* v);

	/*!
	 * \brief The operation of union between the set represented by this object and the
	 * set represented by v.
	 *
	 * This method has the same semantic of setIntersecSet in the vEBTree, but it is
	 * definied to make use of the array structure of this class and get direct acess
	 * to the data structure.
	 *
	 * \param v the set to be operated.
	 */
	virtual void setIntersecSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* ret);

	virtual void setDiffSimetricSet(ArrayvEBTree<T>* v);

	virtual void setDiffSet(ArrayvEBTree<T>* v);

	virtual void setDiffSimetricSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void setDiffSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complUnionSet(ArrayvEBTree<T>* v);

	virtual void complDiffSimetricSet(ArrayvEBTree<T>* v);

	virtual void complIntersecSet(ArrayvEBTree<T>* v);

	virtual void complDiffSet(ArrayvEBTree<T>* v);

	virtual void complUnionSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complDiffSimetricSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complIntersecSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complDiffSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void setUnionCompl(ArrayvEBTree<T>* v);

	virtual void setDiffSimetricCompl(ArrayvEBTree<T>* v);

	virtual void setIntersecCompl(ArrayvEBTree<T>* v);

	virtual void setDiffCompl(ArrayvEBTree<T>* v);

	virtual void setUnionCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void setDiffSimetricCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void setIntersecCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void setDiffCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complUnionCompl(ArrayvEBTree<T>* v);

	virtual void complDiffSimetricCompl(ArrayvEBTree<T>* v);

	virtual void complIntersecCompl(ArrayvEBTree<T>* v);

	virtual void complDiffCompl(ArrayvEBTree<T>* v);

	virtual void complUnionCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complDiffSimetricCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complIntersecCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

	virtual void complDiffCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res);

};

template<typename T>
ArrayvEBTree<T>::~ArrayvEBTree(){
	for(long i = 1; i < vEBTree<T>::height ; i++){
		delete vEBTree<T>::levels[i];
	}
	delete vector;
	delete vEBTree<T>::bitvector;
}

template<typename T>
inline T ArrayvEBTree<T>::treeNode(long i){
	//just retrieve a position in the vector
	return vector[i];
}


template<typename T>
inline ArrayvEBTree<T>::ArrayvEBTree(int sz):vEBTree<T>(sz){
	vectorsz = ((sz >> vEBTree<T>::logb) << vEBTree<T>::logb) == sz? (sz >> vEBTree<T>::logb) : (sz >> vEBTree<T>::logb) + 1;
	if(vectorsz == 0) vectorsz = 1;
	vector = new T[vectorsz];
	vEBTree<T>::levels = new vEBTree<T>*[1];
	vEBTree<T>::levels[0] = this;
	vEBTree<T>::height = 1;
	memset(vector,0, vectorsz*sizeof(T));
}

template<typename T>
ArrayvEBTree<T>::ArrayvEBTree( int size, int ht):vEBTree<T>(size){
	//initialize and allocate memory
	vectorsz = ((size >> vEBTree<T>::logb) << vEBTree<T>::logb) == size? (size >> vEBTree<T>::logb) : (size >> vEBTree<T>::logb) + 1;
	if(vectorsz == 0) vectorsz = 1;
	vector = new T[vectorsz];
	vEBTree<T>::levels = new vEBTree<T>*[ht + 1];
	vEBTree<T>::levels[0] = this;
	memset(vector,0, vectorsz*sizeof(T));
	vEBTree<T>::height = ht + 1;
	int sz = vectorsz;
	for(int i = 1; i <= ht; i++){
		vEBTree<T>::levels[i] = (vEBTree<T>*)new ArrayvEBTree(sz);
		sz = ((sz >> vEBTree<T>::logb) << vEBTree<T>::logb) == sz? (sz >> vEBTree<T>::logb) : (sz >> vEBTree<T>::logb) + 1;
		if(sz == 0) sz = 1;
	}

	//link the upper levels of the current tree
	for(int i = 1; i <=ht; i++){
		vEBTree<T>::levels[i]->levels = (vEBTree<T>**)new ArrayvEBTree<T>*[ht + 1 - i];
		vEBTree<T>::levels[i]->height = ht + 1 - i ;
		vEBTree<T>::levels[i]->levels[0] = vEBTree<T>::levels[i];
		for(int j = i+1; j <= ht; j++){
			vEBTree<T>::levels[i]->levels[j - i] = vEBTree<T>::levels[j];
		}
	}
}

template<typename T>
inline OrderedSet<long>* ArrayvEBTree<T>::clone(){
	//create the copy
	ArrayvEBTree<T>* clone = new ArrayvEBTree(vEBTree<T>::n);
	//copy the whole vector
	for(long i = 0; i < vectorsz; i++){
		clone->vector[i] = vector[i];
	}
	clone->levels[0] = clone;
	for(long j = 1; j < vEBTree<T>::height; j++){
		clone->levels[j] = (vEBTree<T>*)vEBTree<T>::levels[j]->clone();
	}
	return (OrderedSet<long>*)clone;
}

template<typename T>
inline long ArrayvEBTree<T>::bitLeast(long idx, long slide, long h){
	return builtinLeast<T>(((ArrayvEBTree<T>*)vEBTree<T>::levels[h])->vector[idx] & posmasksimp[slide]);
}

template<typename T>
inline long ArrayvEBTree<T>::nextSetElement(long i){

	long h = 0;
	long bit = 0;

	long index[vEBTree<T>::height];
	long slide[vEBTree<T>::height];
	long lim[vEBTree<T>::height];
	index[0] = i >> vEBTree<T>::logb;
	slide[0] = i & vEBTree<T>::maskb;
	lim[0] = ((ArrayvEBTree<T>*)vEBTree<T>::levels[0])->vectorsz;

	bit = bitLeast(index[0], slide[0], 0);

	while(bit == -1 && h < vEBTree<T>::height - 1){
		h++;
		index[h] = index[h-1] << vEBTree<T>::logb;
		slide[h] = index[h-1] & vEBTree<T>::maskb;
		lim[h] = ((ArrayvEBTree<T>*)vEBTree<T>::levels[0])->vectorsz;
		if(++slide[h] >= vEBTree<T>::word_size){
			slide[h] = 0;
			if(++index[h] >= lim[h]) return vEBTree<T>::n+1;
		}
		bit = bitLeast(index[h], slide[h], h);
	}

	while(bit == -1 && index[h] < lim[h] - 1){
		bit = bitLeast(++index[h], 0, h);
	}

	if(bit != -1){
		slide[h] = bit;
		for(long i = h - 1 ; i >= 0; i--){
			index[i] = (index[i+1] << vEBTree<T>::logb) + slide[i+1];
			if(index[i] >= lim[i]) return vEBTree<T>::n+1;
			slide[i] = bitLeast(index[i], 0, i);
		}
		return (index[0] << vEBTree<T>::logb) + slide[0];
	}

	return vEBTree<T>::n+1;
}

template<typename T>
inline long ArrayvEBTree<T>::nextSetElementInLevel(long i){

	if(i >= vEBTree<T>::n) return -1;

	long index = wordIdx(i);//index of the word

	//look in the word of i for the next one
	long inword = builtinLeast<T>(vector[index] & posmasklsimp[inWordIdx(i)]);

	//if a found it, return
	if(inword != -1) return inword  + (index << vEBTree<T>::logb);

	//look in the rest of the vector
	index++;
	for(long j = index; j < vectorsz; j++){
		inword = builtinLeast<T>(vector[j]);
		if(inword > 0) return inword + (j << vEBTree<T>::logb) ;
	}
	return -1;
}

template<typename T>
inline long ArrayvEBTree<T>::nextComplElementInLevel(long i){
	//for each element, tests if it is in the complement
	for(long j = i; j < vEBTree<T>::n; j++){
		if(isInCompl(j)) return j;
	}
	return -1;
}

template<typename T>
inline long ArrayvEBTree<T>::inWordIdx(long i){
	return i & vEBTree<T>::maskb;
}

template<typename T>
inline long ArrayvEBTree<T>::wordIdx(long i){
	return i >> vEBTree<T>::logb;
}

template<typename T>
inline void ArrayvEBTree<T>::toSetInLevel(long i){
	vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
}

template<typename T>
inline void ArrayvEBTree<T>::toComplInLevel(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
}

template<typename T>
inline void ArrayvEBTree<T>::toSet(long i){
	vector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
	int j = 1,index = wordIdx(i);

	//update the summary vector if necessary
	while(j < vEBTree<T>::height && vEBTree<T>::levels[j]->isInCompl(index)){
		vEBTree<T>::levels[j]->toSetInLevel(index);
		index = vEBTree<T>::levels[j]->wordIdx(index);
		j++;
	}
}

template<typename T>
inline void ArrayvEBTree<T>::toCompl(long i){
	vector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
	int j = 1,index = wordIdx(i);
	T word = 0;

	//update the summary vector if necessary
	while(word == 0 && j < vEBTree<T>::height){
		vEBTree<T>::levels[j]->toComplInLevel(index);
		word = vEBTree<T>::levels[j]->treeNode(index);
		index = vEBTree<T>::levels[j]->wordIdx(index);
		j++;
	}
}


template<typename T>
inline bool ArrayvEBTree<T>::isInSet(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) != 0;
}

template<typename T>
inline bool ArrayvEBTree<T>::isInCompl(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) == 0;
}


template<>
inline long ArrayvEBTree<int>::nextSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
}

template<>
inline long ArrayvEBTree<long>::nextSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
}

template<>
inline long ArrayvEBTree<int>::firstSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>(vector[i]) ;
}

template<>
inline long ArrayvEBTree<long>::firstSetInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>(vector[i]) ;
}

template<>
inline long ArrayvEBTree<int>::firstComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>(~vector[i]) ;
}

template<>
inline long ArrayvEBTree<long>::firstComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>(~vector[i]) ;
}

template<>
inline long ArrayvEBTree<int>::nextComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<int>((~vector[wordIdx(i)]) & posmasksimp[inWordIdx(i)]);
}

template<>
inline long ArrayvEBTree<long>::nextComplInWord(long i){
	//using builtin to look inside a word
	return builtinLeast<long>((~vector[wordIdx(i)]) & posmasksimp[inWordIdx(i)]);
}


template<>
inline long ArrayvEBTree<int>::countSetInWord(long i){
	//using builtin to count
	return builtinCounter<int>(vector[i]);
}

template<>
inline long ArrayvEBTree<long>::countSetInWord(long i){
	//using builtin to count
	return builtinCounter<long>(vector[i]);
}

template<>
inline long ArrayvEBTree<int>::countComplInWord(long i){
	//using builtin to count
	return builtinCounter<int>(~vector[i]);
}

template<>
inline long ArrayvEBTree<long>::countComplInWord(long i){
	//using builtin to count
	return builtinCounter<long>(~vector[i]);
}

template<typename T>
inline bool ArrayvEBTree<T>::setNode(long i, T newnode){
	vector[i] = newnode;

	//if has a upper vector, update it
	if(vEBTree<T>::height > 1){
		if(newnode == 0)vEBTree<T>::levels[1]->toCompl(i);
		else vEBTree<T>::levels[1]->toSet(i);
	}
	return true;
}

template<typename T>
inline bool ArrayvEBTree<T>::setNodeInLevel(long i, T newnode){
	vector[i] = newnode;
	return true;
}

template<typename T>
inline long* ArrayvEBTree<T>::toArray(long* size){
	vEBTree<T>::bitvector = new long[vectorsz];
	for(*size = 0; *size < vectorsz; (*size)++){
		vEBTree<T>::bitvector[*size] = vector[*size];
	}
	return vEBTree<T>::bitvector;
}

template<typename T>
inline long ArrayvEBTree<T>::size(){
	return vEBTree<T>::n;
}

template<typename T>
inline long ArrayvEBTree<T>::sizeInWord(){
	return vectorsz;
}

template<typename T>
inline void ArrayvEBTree<T>::allToSetInLevel(){
	memset(vector, 255, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayvEBTree<T>::allToSet(){
	memset(vector, 255, vectorsz*sizeof(T));
	for(long i = 1; i < vEBTree<T>::height; i++){
		vEBTree<T>::levels[i]->allToSetInLevel();
	}
}

template<typename T>
inline void ArrayvEBTree<T>::allToComplInLevel(){
	memset(vector, 0, vectorsz*sizeof(T));
}

template<typename T>
inline void ArrayvEBTree<T>::allToCompl(){
	memset(vector, 0, vectorsz*sizeof(T));
	for(long i = 1; i < vEBTree<T>::height; i++){
		vEBTree<T>::levels[i]->allToComplInLevel();
	}
}

template<typename T>
inline void ArrayvEBTree<T>::setUnionSet(ArrayvEBTree<T>* v){
	long ht = vEBTree<T>::height;
	long size;
	ArrayvEBTree<T>* up;
	T* avec;
	T* bvec;
	T* lim;

	avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vector;
	bvec = ((ArrayvEBTree<T>*)(v->vEBTree<T>::levels[ht-1]))->vector;
	lim = avec + ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vectorsz;
	for(; avec < lim; avec++ , bvec ++) *avec |= *bvec;

	for(long i = ht-2; i >= 0; i--){
		up = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i+1]);
		bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[i])->vector;
		avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i])->vector;
		size = up->size();
		long j = up->nextSetElement(0);
		while(j < size-1){
			avec[j] |= bvec[j];
			j = up->nextSetElement(j+1);
		}
		avec[size-1] |= bvec[size-1];
	}
}

template<typename T>
inline void ArrayvEBTree<T>::setUnionSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* ret){
	long ht = vEBTree<T>::height;
	long size;
	ArrayvEBTree<T>* up;
	T* avec;
	T* bvec;
	T* cvec;
	T* lim;

	avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vector;
	bvec = ((ArrayvEBTree<T>*)(v->vEBTree<T>::levels[ht-1]))->vector;
	cvec = ((ArrayvEBTree<T>*)(ret->vEBTree<T>::levels[ht-1]))->vector;
	lim = avec + ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vectorsz;
	for(; avec < lim; avec++ , bvec++, cvec++) *cvec = *avec | *bvec;

	for(long i = ht-2; i >= 0; i--){
		up = ((ArrayvEBTree<T>*)ret->vEBTree<T>::levels[i+1]);
		bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[i])->vector;
		avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i])->vector;
		cvec = ((ArrayvEBTree<T>*)ret->vEBTree<T>::levels[i])->vector;
		size = up->size();
		long j = up->nextSetElement(0);
		while(j < size-1){
			cvec[j] = avec[j] | bvec[j];
			j = up->nextSetElement(j+1);
		}
		cvec[size-1] = avec[size-1] | bvec[size-1];
	}
}


template<typename T>
inline void ArrayvEBTree<T>::setIntersecSet(ArrayvEBTree<T> * v){
	long ht = vEBTree<T>::height;
	long size;
	ArrayvEBTree<T>* up;
	T* avec;
	T* bvec;
	T* lim;

	avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vector;
	bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[ht-1])->vector;
	lim = avec + ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vectorsz;
	for(; avec < lim; avec++ , bvec++) *avec &= *bvec;

	for(long i = ht-2; i >= 0; i--){
		up = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i+1]);
		bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[i])->vector;
		avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i])->vector;
		size = up->size();
		for(long j = up->nextSetElement(0); j < size-1; j = up->nextSetElement(j+1)){
			avec[j] &= bvec[j];
			if(avec[j] == 0)up->toComplInLevel(j);
		}
		avec[size-1] &= bvec[size-1];
	}
}

template<typename T>
inline void ArrayvEBTree<T>::setIntersecSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* ret){
	long ht = vEBTree<T>::height;
	long size;
	ArrayvEBTree<T>* up;
	T* avec;
	T* bvec;
	T* cvec;
	T* lim;

	avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vector;
	bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[ht-1])->vector;
	cvec = ((ArrayvEBTree<T>*)ret->vEBTree<T>::levels[ht-1])->vector;
	lim = avec + ((ArrayvEBTree<T>*)vEBTree<T>::levels[ht-1])->vectorsz;
	for(; avec < lim; avec++ , bvec++) *cvec = *avec & *bvec;

	for(long i = ht-2; i >= 0; i--){
		up = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i+1]);
		bvec = ((ArrayvEBTree<T>*)v->vEBTree<T>::levels[i])->vector;
		bvec = ((ArrayvEBTree<T>*)ret->vEBTree<T>::levels[i])->vector;
		avec = ((ArrayvEBTree<T>*)vEBTree<T>::levels[i])->vector;
		size = up->size();
		for(long j = up->nextSetElement(0); j < size-1; j = up->nextSetElement(j+1)){
			cvec[j] = avec[j] & bvec[j];
			if(cvec[j] == 0)up->toComplInLevel(j);
		}
		cvec[size-1] = avec[size-1] & bvec[size-1];
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSimetricSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] ^= bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec ^= *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] &= ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec &= ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSimetricSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] ^ bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec ^ *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complUnionSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] | bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec | *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSimetricSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] ^ bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec ^ *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complIntersecSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec & *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSet(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complUnionSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] | bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec | *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSimetricSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] ^ bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec ^ *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complIntersecSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec & *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSet(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setUnionCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = avec[i] | ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = *avec | ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSimetricCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = avec[i] ^ ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = *avec ^ ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setIntersecCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = *avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = *avec & *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setUnionCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] | ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec | ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffSimetricCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] ^ ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec ^ ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setIntersecCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::setDiffCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = *avec & *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complUnionCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] | ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec | ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSimetricCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] ^ ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec ^ ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complIntersecCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffCompl(ArrayvEBTree<T>* v){
	T* avec = vector;
	T* bvec = v->vector;
	T* lim = vector + vectorsz;

	if(vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((avec[i] = ~avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++){
			*avec = ~*avec & *bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complUnionCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] | ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffSimetricCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] ^ ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec ^ ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complIntersecCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] & ~bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec & ~*bvec;
		}
	}
}

template <typename T>
inline void ArrayvEBTree<T>::complDiffCompl(ArrayvEBTree<T>* v, ArrayvEBTree<T>* res){
	T* avec = vector;
	T* bvec = v->vector;
	T* cvec = res->vector;
	T* lim = res->vector + res->vectorsz;

	if(res->vEBTree<T>::height > 1){
		ArrayvEBTree<T>* up = (ArrayvEBTree<T>*)res->vEBTree<T>::levels[1];
		for(long i = 0 ; i < vectorsz; i++){
			if((cvec[i] = ~avec[i] & bvec[i]) == 0)up->toCompl(i);
			else up->toSet(i);
		}
	}else{
		for(; avec < lim; avec++, bvec++, cvec++){
			*cvec = ~*avec & *bvec;
		}
	}
}

//Iterator

template<typename T>
ArrayvEBTree<T>::Iterator::Iterator(ArrayvEBTree<T>* t){
	//alocate memory
	ht = t->vEBTree<T>::height;
	logb = t->vEBTree<T>::logb;
	levels = new T*[ht];
	lims = new long[ht];
	slides = new long[ht];
	idxs = new long[ht];

	//copy the reference to all the levels
	for(long i = 0; i < ht; i++){
		levels[i] = ((ArrayvEBTree*)t->vEBTree<T>::levels[i])->vector;
		lims[i] = ((ArrayvEBTree*)t->vEBTree<T>::levels[i])->vectorsz;
	}

	//copy same inner variables
	word_size = t->word_size;
	size = t->size();
	current = 0;
}

template<typename T>
ArrayvEBTree<T>::Iterator::~Iterator(){
	//clean memory
	delete levels;
	delete slides;
	delete idxs;
}

template<typename T>
inline long ArrayvEBTree<T>::Iterator::bitLeast(long idx, long slide, long h){
	return builtinLeast<T>(levels[h][idx] & posmasksimp[slide]);
}

template<typename T>
inline void ArrayvEBTree<T>::Iterator::start(){
	//initialize the variables
	for(long i = 0; i < ht; i++){
		slides[i] = 0;
		idxs[i] = 0;
	}

	//look for the first
	long h = ht - 1 ;
	long bit ;
	idxs[h] = -1;
	//search in the higher level
	do{
		idxs[h]++;
		bit = bitLeast(idxs[h], slides[h], h);
	}while(bit == -1 && idxs[h] < lims[h]);

	//if not found
	if(idxs[h] == lims[h])
		current = size + 1;
	else{
		//down in the tree
		slides[h] = bit;
		for(; h > 0; h--) {
			idxs[h-1] = (idxs[h] << logb) + slides[h];
			if(idxs[h-1] >= lims[h-1]){
				current = -1;
				return;
			}
			slides[h-1] = bitLeast(idxs[h-1], 0, h-1);
		}
		current = (idxs[0] << logb) + slides[0];
	}
}

template<typename T>
inline void ArrayvEBTree<T>::Iterator::restart(){
	start();
}

template<typename T>
inline void ArrayvEBTree<T>::Iterator::restartFrom(long i){
	//initialize
	start();
	if(i >= lims[0]) current = size + 1;
	else{
		//walk untill pass the especified position
		while(current < i )next();
	}
}

template<typename T>
inline bool ArrayvEBTree<T>::Iterator::hasNext(){
	return current < size;
}

template<typename T>
inline long ArrayvEBTree<T>::Iterator::next(){
	long ret = current;
	long h = 0;
	long bit = 0;
	//look in the bottom level
	if(++slides[h] >= word_size){
		slides[h] = 0;
		if(++idxs[h] >= lims[h]){
			current = size+1;
			return ret;
		}
	}
	bit = bitLeast(idxs[h], slides[h], h);
	//going up in the tree
	while(bit == -1 && h < ht - 1 ){
		h++;
		if(++slides[h] >= word_size){
			slides[h] = 0;
			if(++idxs[h] >= lims[h]){
				current = size+1;
				return ret;
			}
		}
		bit = bitLeast(idxs[h], slides[h], h);
	}

	//look in the higher level
	while(bit==-1 && idxs[h]++ < lims[h] - 1){
		bit = bitLeast(idxs[h], slides[h], h);
	}
	//if not found
	if(idxs[h] == lims[h]) current = size + 1 ;
	else{
		//going down in the tree
		slides[h] = bit;
		for(; h > 0; h--) {
			idxs[h-1] = (idxs[h] << logb) + slides[h];
			if(idxs[h-1] >= lims[h-1]){
				current = -1;
				return ret;
			}
			slides[h-1] = bitLeast(idxs[h-1], 0, h-1);
		}
		current = (idxs[0] << logb) + slides[0];
	}
	return ret;
}

template<typename T>
ArrayvEBTree<T>::FilterIterator::FilterIterator(ArrayvEBTree<T>* t, OrderedSet<long>* filter){
	this->filter = filter;
	ht = t->vEBTree<T>::height;
	logb = t->vEBTree<T>::logb;
	levels = new T*[ht];
	lims = new long[ht];
	slides = new long[ht];
	idxs = new long[ht];
	for(long i = 0; i < ht; i++){
		levels[i] = ((ArrayvEBTree*)t->vEBTree<T>::levels[i])->vector;
		lims[i] = ((ArrayvEBTree*)t->vEBTree<T>::levels[i])->vectorsz;
	}
	word_size = t->word_size;
	size = t->size();
	current = 0;
}

template<typename T>
ArrayvEBTree<T>::FilterIterator::~FilterIterator(){
	delete levels;
	delete slides;
	delete idxs;
}

template<typename T>
inline long ArrayvEBTree<T>::FilterIterator::bitLeast(long idx, long slide, long h){
	return builtinLeast<T>(levels[h][idx] & posmasksimp[slide]);
}

template<typename T>
inline void ArrayvEBTree<T>::FilterIterator::start(){
	for(long i = 0; i < ht; i++){
		slides[i] = 0;
		idxs[0] = 0;
	}

	//look for the first
	long h = ht;
	long bit ;

	do{
		bit = bitLeast(idxs[h]++, slides[h], h);
	}while(bit==-1 && idxs[h] < lims[h]);

	if(idxs[h] == lims[h])
		current = size + 1;
	else{
		slides[h] = bit;
		for(; h > 0; h--) {
			idxs[h-1] = (idxs[h] << logb) + slides[h];
			if(idxs[h-1] >= lims[h-1]){
				current = -1;
				return;
			}
			slides[h-1] = bitLeast(idxs[h-1], 0, h-1);
		}
		current = (idxs[0] << logb) + slides[0];
		if(filter->isInCompl(current))next();
	}
}

template<typename T>
inline void ArrayvEBTree<T>::FilterIterator::restart(){
	start();
}

template<typename T>
inline void ArrayvEBTree<T>::FilterIterator::restartFrom(long i){
	start();
	if(i >= lims[0]) current = size + 1;
	else{
		while(current < i )next();
	}
}

template<typename T>
inline bool ArrayvEBTree<T>::FilterIterator::hasNext(){
	return current < size;
}

template<typename T>
inline long ArrayvEBTree<T>::FilterIterator::next(){
	//initialize the variables
	long ret = current;

	long h = 0;
	long bit ;
	do{
		if(++slides[h] >= word_size){
			slides[h] = 0;
			if(++idxs[h] >= lims[h]){
				current = size+1;
				return ret;
			}
		}
		bit = bitLeast(idxs[h], slides[h], h);
		while(bit == -1 && h < ht - 1 ){
			h++;
			if(++slides[h] >= word_size){
				slides[h] = 0;
				if(++idxs[h] >= lims[h]){
					current = size+1;
					return ret;
				}
			}
			bit = bitLeast(idxs[h], slides[h], h);
		}

		while(bit==-1 && idxs[h]++ < lims[h] - 1){
			bit = bitLeast(idxs[h], slides[h], h);
		}
		if(idxs[h] == lims[h]) current = size + 1 ;
		else{
			slides[h] = bit;
			for(; h > 0; h--) {
				idxs[h-1] = (idxs[h] << logb) + slides[h];
				if(idxs[h-1] >= lims[h-1]){
					current = -1;
					return ret;
				}
				slides[h-1] = bitLeast(idxs[h-1], 0, h-1);
			}
			current = (idxs[0] << logb) + slides[0];
		}
	}while(filter->isInCompl(current) && current < size);
	return ret;
}

template<typename T>
inline bool ArrayvEBTree<T>::isEmpty(){
	T* top = ((ArrayvEBTree*)vEBTree<T>::levels[vEBTree<T>::height -1])->vector;
	T* lim = ((ArrayvEBTree*)vEBTree<T>::levels[vEBTree<T>::height -1])->vectorsz + top;
	for(;top < lim; top++){
		if(*top != 0) return false;
	}
	return true;
}

template <typename T>
class ArrayvEBTreeFactory : public OrderedSetFactory<long>{
public:

	OrderedSet<long>* newOrderedSet(long n){
		return (OrderedSet<long>*) new ArrayvEBTree<T>(n);
	};

	OrderedSet<long>* newOrderedSet(long n, void* handle){
		return (OrderedSet<long>*)new ArrayvEBTree<T>( n, *(long*)handle);
	};

};

#endif /* ARRAYVEBTREE_H_ */
